1. Technical Field
The present invention relates to a method and apparatus for compressing data in general, and in particular to a method and apparatus for performing adaptive data compression. Still more particularly, the present invention relates to a method and apparatus for encoding Lempel-Ziv 1 variants.
2. Description of the Prior Art
The volume of digital data utilized to represent information in computers and workstations, as well as the speed with which these data must be compressed and decompressed in the course of storage or transmission has motivated significant interest in technologies related to data compression. A data compression algorithm that has proven to be quite popular was first described in an article entitled "A Universal Algorithm for Sequential Data Compression" by J. Ziv and A. Lempel, as appeared in IEEE Transactions on Information Theory, vol. IT-23, no. 3, pp. 337-343, 1977. This data compression algorithm is generally referred to as the LZ.sub.-- 1 algorithm. The original LZ.sub.-- 1 algorithm has since been refined in various aspects by numerous investigators. Examples of these so-called LZ.sub.-- 1 variants can be found in U.S. Pat. No. 5,003,307 and U.S. Pat. No. 5,146,221, the subject matter of which is incorporated by reference herein.
Other examples of Lempel-Ziv 1 variants include Adaptive Lossless Data Compression (ALDC) that is widely utilized for general purpose data compression within computers and associated peripheral devices. ALDC is described in full detail in "QIC Development Standard QIC-154," Rev. A, 10 Mar. 1994, Quarter-Inch Cartridge Drive Standards, Inc., the subject matter of which is also incorporated by reference herein.
The fundamental concepts that characterize these and other LZ.sub.-- 1 variants involve the usage of a history-buffer to store new data and to identify new strings of data that match any previously received and processed data. Thereby, new strings of data, typically alphanumeric characters, which match existing strings can be identified by merely referring to an offset (or displacement) and a length in an earlier point of the string sequence within the history-buffer. The LZ.sub.-- 1 algorithm is adaptive because each new data byte is entered into the history-buffer in sequence, and displaces the oldest stored byte if the history-buffer is full. The size of the history-buffer is thus analogous to a sliding window over a data stream in which the new data characters are always compared to previously received characters within the length of the window. The encoded output is a mixture of LITERAL.sub.-- DATA, where no compression is possible, or COPY.sub.-- POINTERs, providing a length and offset identifying a matching previously existing character string within the window. As would be expected, the algorithm is increasingly effective as the size of the window increases and repetition of the patterns in the data characters within the window increases.
The present disclosure describes an improved method and apparatus for encoding these Lempel-Ziv 1 variants.